package oj;

/**
 * @author 郝文雪
 * @date 2022/9/2 13:55
 * @Description Test
 */
public class LC416 {
    //一维数组
    public boolean canPartition(int[] nums) {
        int len=nums.length;
        int sum=0;
        for(int num:nums){
            sum+=num;
        }
        if((sum&1)==1){
            return false;
        }
        int target=sum>>1;
        boolean[] dp=new boolean[target+1];
        dp[0]=true;
        if(nums[0]<=target){
            dp[nums[0]]=true;
        }

        for(int i=1;i<len;i++){
            for(int j=target;j>=nums[i];j--){
                if(dp[target]){
                    return true;
                }
                if(nums[i]<j){
                    dp[j]=dp[j] || dp[j-nums[i]];
                }
            }
        }
        return dp[target];
    }


    //二维数组
//    public boolean canPartition(int[] nums) {
//        int len=nums.length;
//        int sum=0;
//        for(int num:nums){
//            sum+=num;
//        }
//        if((sum&1)==1){
//            return false;
//        }
//        int target=sum>>1;
//        boolean[][] dp=new boolean[len][target+1];
//        if(nums[0]<=target){
//            dp[0][nums[0]]=true;
//        }
//        dp[0][0]=true;
//        for(int i=1;i<len;i++){
//            for(int j=0;j<=target;j++){
//                dp[i][j]=dp[i-1][j];
//                if(nums[i]==j){
//                    dp[i][j]=true;
//                    continue;
//                }
//                if(nums[i]<j){
//                    dp[i][j]=dp[i-1][j] || dp[i-1][j-nums[i]];
//                }
//            }
//        }
//        return dp[len-1][target];
//    }


}
